package com.zhuhao.sort;

import java.util.Arrays;

/**
 * 希尔排序(Shell Sort): https://www.runoob.com/data-structures/shell-sort.html
 * <p>
 * 是插入排序的一种，它是针对直接插入排序算法的改进。
 * 它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
 * <p>
 * 希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，
 * 因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。
 *
 * 算法稳定性 不稳定排序算法
 *
 * @Author zhuhao
 * @Date 2021/8/16 0016 10:50
 * @desc
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] internalSort = {7, 6, 9, 3, 1, 5, 2, 4};
        shellSort(internalSort);
    }

    public static void shellSort(int[] arr) {
        System.out.println(Arrays.toString(arr));
        for (int step = arr.length / 2; step > 0; step /= 2) {
            System.out.println(step);
            for (int i = step; i < arr.length; i++) {
                int value = arr[i];
                int j;
                for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                    System.out.println(Arrays.toString(arr));
                    arr[j + step] = arr[j];
                    System.out.println(Arrays.toString(arr));
                }
                System.out.println(Arrays.toString(arr));
                arr[j + step] = value;
                System.out.println(Arrays.toString(arr));
            }
        }

        System.out.println(Arrays.toString(arr));
    }

}
